The present invention generally relates to multiple links within a communication span between two devices in a network. More specifically, the present invention relates to a method and apparatus for load balancing among multiple links for a next-hop device within a label switched network.
Multiple links technique is widely used as a simple way to enhance bandwidth between two communicating devices or nodes in a network. For example, in a wavelength division multiplexing network, parallel links are established using multiple wavelengths that are isolated from each other. Multiple links can be established on either physically separate media, such as several fibers and/or several wavelengths in an optical fiber, or several slots in a shared medium where some multiplexing technology is applied, such as several VC's (virtual containers) in STM (synchronous transfer module) on SONET (synchronous optical network)/SDH (synchronous digital hierarchy).
Some early methods, known as link costs tuning, were used to provide load balancing among multiple links involved changing link costs according to loading, where link costs were used in the routing algorithm to find the shortest link or path for each pair of source and destination. These methods proved to be unsatisfactory partly due to coarse granularity in adjustment and traffic oscillation resulting from inherent instability caused by delay in the feedback process.
The “Equal Cost Multipath (ECMP)” method is another method used to achieve load balancing among multiple links. In the ECMP method, no attempt is made to make dynamic adjustments to OSPF costs based on loading thereby causing the ECMP method to be reliable. If the topology is such that equal cost paths exists, then an attempt is made to divide traffic equally among the paths. The following methods of dividing traffic have been used.
The “per packet round robin forwarding” method is applicable only if the delays on the paths are almost equal. The delay difference must be small relative to packet serialization time. Delay differences greater than three times the packet serialization time can cause terrible TCP performance degradation because arrivals of incorrectly-ordered packets will trigger TCP fast retransmit, thus limiting TCP to a small window and very poor performance over long delay path.
The “source/destination hash” method was used as far back as the T1-NSFNET in the IBM RT-PC based routers. A hash function, such as CRC-16, is applied over the source address and destination address. The hash space is then split evenly among the available paths by either setting thresholds or performing a modulo operation. Traffic between any given source and destination remain on the same path.
These methods described here are based on the IP packet forwarding mechanism. Hence, they do not support any signaling mechanism to reserve resources along a route where each packet is forwarded. Neither do they support explicit routing to realize the traffic engineering. Hence, it would be desirable to provide a method and apparatus which is capable of performing load balancing without using any IP packet forwarding mechanism.
Moreover, using multiple links may incur one or more possible drawbacks. For example, degraded efficiency in link utilization may result under unbalanced traffic without load balancing. FIG. 1 illustrates this situation. Severe packet loss may occur on congested physical link #1 even if the other links, such as links #2 and #3, are unused. Without load balancing, over engineering is done to reduce packet loss within the multiple links. FIG. 2 illustrates a situation in which conventional loading balancing is performed. As shown in FIG. 2, packets belonging to the same class are forwarded into a specific one of the multiple links to help evenly distribute or balance the traffic across all the multiple links. When a packet is distributed from one physical link to another, the associated label is also changed. For example, if packet with label A in physical link #1 is re-routed onto physical link #2, the packet is given a new label A′ in physical link #2.
Load balancing across multiple links generates a significant amount of processing overhead in some networks, such as, a multiple protocol label switched (MPLS) network. In a conventional MPLS network, each packet is given a label and the transport of a packet depends on its label. Packets having the same labels are treated in an identical manner, e.g., they are all routed along a previously setup label switched path or link. In this type of network, when packets are re-routed from one link to another due to, e.g., congestion, the re-routed packets need to be given new labels for transport along the new link. This need to create new labels results in a large amount of processing overhead. For example, a new label switched path need to be set up and the new label forwarding information need to be distributed to all the nodes along the new label switch path. In a MPLS network with massively parallel multiple links, load balancing may become problematic. Hence, it would also be desirable to provide a method and apparatus which is capable of performing load balancing across multiple links in a network, such as, the MPLS network while maintaining a satisfactory level of processing overhead.
Furthermore, in a MPLS network, when an incoming packet is received by a label switching router, the label associated with the incoming packet is changed or mapped to a new label for delivery to the next label switching router. This label mapping process is performed by looking up the relevant label forwarding information in an associated label forwarding table. The associated label forwarding table typically contains all the entries forwarded to the label switching router via all the multiple links. The number of entries for all the multiple links can be quite large. Consequently, the search time for the relevant label forwarding information at each label switching router may be substantial thereby delaying the label mapping process which in turn affects the transmission latency of the packets. Therefore, it would further be desirable to provide a method and apparatus which is capable of improving the transmission latency of a network, such as, the MPLS network.